#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 50005;
int maxst[maxn][20],minst[maxn][20],n,q;

void init(){
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)<=n+1;i++){
			maxst[i][j]=max(maxst[i][j-1],maxst[i+(1<<(j-1))][j-1]);
			minst[i][j]=min(minst[i][j-1],minst[i+(1<<(j-1))][j-1]);
		}
	}
}

int query(int l,int r){
	int k=0;
	while((1<<k)<=(r-l+1))k++;
	k--;
	return max(maxst[l][k],maxst[r-(1<<k)+1][k])-min(minst[l][k],minst[r-(1<<k)+1][k]);
}

int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>maxst[i][0];
		minst[i][0]=maxst[i][0];
	}
	init();
	int a,b;
	for(int i=1;i<=q;i++){
		cin>>a>>b;
		if(a==b){
			cout<<0<<endl;
			continue;
		} 
		cout<<query(a,b)<<endl;
	}
	
}
